import collections
import copy
from typing import List


class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        """
        从后往前，去掉一条边以后，对每个节点进行并查集的处理。
        进行路径优化
        """

        relations = collections.defaultdict(set)

        crash = None
        nodeIDs = set()
        for edge in edges:
            father, child = edge
            relations[child].add(father)
            nodeIDs.add(child)
            if len(relations[child]) > 1:
                crash = child

        def isRing(relations):

            def closure(nodeID):
                visited = set()
                new = {nodeID}
                while new:
                    tmp = set()
                    for nID in new:
                        for fID in relations[nID]:
                            if fID not in visited:
                                tmp.add(fID)
                    visited = visited | tmp
                    new = tmp
                return visited

            ring = set()
            for nodeID in nodeIDs:
                if nodeID in closure(nodeID):
                    ring.add(nodeID)
            return (True, ring) if ring else (False, ring)

        if crash:
            for edge in edges[::-1]:
                f, c = edge
                if c == crash:
                    rs = copy.deepcopy(relations)
                    rs[c].remove(f)
                    flag, ring = isRing(rs)
                    if flag == False:
                        return edge
        else:
            rs = copy.deepcopy(relations)
            flag, ring = isRing(rs)
            for edge in edges[::-1]:
                f, c = edge
                if (f in ring) and (c in ring):
                    return edge


edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]
print(Solution().findRedundantDirectedConnection(edges))
